/*
不使用任何内建的哈希表库设计一个哈希集合

具体地说，你的设计应该包含以下的功能

add(value)：向哈希集合中插入一个值。
contains(value) ：返回哈希集合中是否存在这个值。
remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-hashset
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/*

为了实现 HashSet 数据结构，有两个关键的问题，即哈希函数和冲突处理。

哈希函数：目的是分配一个地址存储值。理想情况下，每个值都应该有一个对应唯一的散列值。
冲突处理：哈希函数的本质就是从 A 映射到 B。但是多个 A 值可能映射到相同的 B。这就是碰撞。因此，我们需要有对应的策略来解决碰撞。总的来说，有以下几种策略解决冲突：
单独链接法：对于相同的散列值，我们将它们放到一个桶中，每个桶是相互独立的。
开放地址法：每当有碰撞， 则根据我们探查的策略找到一个空的槽为止。
双散列法：使用两个哈希函数计算散列值，选择碰撞更少的地址。

作者：LeetCode
链接：https://leetcode-cn.com/problems/design-hashset/solution/she-ji-ha-xi-ji-he-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

#define ArrayLen 499
class MyHashSet {
private:
    vector<int>* arr[ArrayLen] = {0};
public:
    /** Initialize your data structure here. */
    MyHashSet() {

    }
    
    void add(int key) {
        if(contains(key))
            return;
        int newkey = key % ArrayLen;
        if(arr[newkey] == 0)
        {
            arr[newkey] = new vector<int>;
            arr[newkey]->push_back(key);
        }
        else
        {
            arr[newkey]->push_back(key);
        }
    }
    
    void remove(int key) 
    {
        int newkey = key % ArrayLen;
        if(arr[newkey] == 0)
        {
            return;
        }
        
        for(vector<int>::iterator iter=arr[newkey]->begin(); iter!=arr[newkey]->end(); iter++)
        {
            if( *iter == key)
            {
                arr[newkey]->erase(iter);
                break;
            }
                    
        }
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        int newkey = key % ArrayLen;
        if(arr[newkey] == 0)
        {
            return false;
        }
        for(vector<int>::iterator iter=arr[newkey]->begin(); iter!=arr[newkey]->end(); iter++)
        {
            if( *iter == key)
            
                    return true;
        }
        return false;
    }
};


/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */